#pragma once

#include "RBTree.h"

namespace byh
{
	template<typename K, typename V>
	class map
	{
	private:
		struct MapKeyOfT
		{
			const K& operator()(const std::pair<K, V>& kv)
			{
				return kv.first;
			}
		};

	public:
		typedef typename RBTree<K, std::pair<const K, V>, MapKeyOfT>::iterator iterator;
		typedef typename RBTree<K, std::pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;

		std::pair<iterator, bool> insert(const std::pair<K, V>& kv)
		{
			return _tree.insert(kv);
		}

		iterator find(const K& key)
		{
			return _tree.find(key);
		}

		iterator begin()
		{
			return _tree.begin();
		}

		iterator end()
		{
			return _tree.end();
		}

		const_iterator begin() const
		{
			return _tree.begin();
		}

		const_iterator end() const
		{
			return _tree.end();
		}

		V& operator[](const K& key)
		{
			std::pair<iterator, bool> ret = this->insert(std::make_pair(key, V()));
			return ret.first->second;
		}

	private:
		RBTree<K, std::pair<const K, V>, MapKeyOfT> _tree;
	};

	void Test_map()
	{
		//map<char, int> m;
		//m.insert({ 'e', 1 });
		//m.insert({ 'f', 1 });
		//m.insert({ 'b', 1 });
		//m.insert({ 'j', 1 });
		//m.insert({ 'l', 1 });
		//m.insert({ 'k', 1 });

		//map<char, int>::iterator it = m.begin();
		//while (it != m.end())
		//{
		//	// it->first = 'e';
		//	std::cout << it->first << " " << it->second << std::endl;
		//	++ it;
		//}
		//std::cout << std::endl;

		//map<char, int>::iterator it = m.find('k');
		//while (it != m.end())
		//{
		//	// it->first = 'e';
		//	std::cout << it->first << " " << it->second << std::endl;
		//	--it;
		//}
		//std::cout << std::endl;

		std::vector<std::string> v = { "apple", "tassel", "watermelon", "apple", "banana", "tassel", "orange", "apple" };
		map<std::string, int> m;
		for (auto& e : v) m[e] ++;
		for (auto& it : m)
		{
			std::cout << it.first << " " << it.second << std::endl;
		}
	}
}